﻿//*************************************************************************
//面向服务的协作式智能交通系统仿真软件SoC-ITSS v2.1 alpha
//发布单位：西北工业大学--巴黎高科MINES机器人与群智能系统联合实验室
//团队负责人：张凯龙 Zhang Kailong
//团队成员：张大方、杨安胜、王敏、谢策、王雨佳、谢尘玉等
//联系我们：kl.zhang@nwpu.edu.cn
//2012-2021
//*************************************************************************


using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using System.Threading.Tasks;

//*******************************************************
//
//文件名(File Name):           VehiclePathDijsktra_Sche.cs
//
//数据表(Tables):              nothing
//
//          修改理由：        根据需求修改Dijsktra算法
//
//*******************************************************

namespace CyberCarSimulation.Algorithm
{
    class VehiclePathDijsktra_Sche
    {
        //道路网络的邻接矩阵        
        static int[,] Metro = new int[6, 6] { 
                { 0,    1,    2048,  1,    2048, 2048},
                { 1,    0,    1,     2048, 1,    2048},
                { 2048, 1,    0,     2048, 2048, 1},
                { 1,    2048, 2048,  0,    1,    2048},
                {2048,  1,    2048,  1,    0,    1},
                {2048,  2048, 1,     2048, 1,    0}};
        static private int row = 6;    
        public static string[,] PathRoutingtable = new string[row, row];

        int[] distance = new int[row];
        int[] prev = new int[row];  
      

        /// <summary>
        /// Dijsktra算法的实现部分
        /// </summary>
        /// <param name="Start"></param>
        private void FindWay(int Start)
        {
            ArrayList S = new ArrayList(row);//S储存确定最短路径的顶点的下标
            ArrayList U = new ArrayList(row);//U中存储尚未确定路径的顶点的下标
            distance = new int[row];         //存储start节点到其他节点的距离
            prev = new int[row];

            
            //标记位
            List<bool> Isfor = new List<bool>();
            for (int temp = 0; temp < row; temp++) 
            {
                Isfor.Add(false);
            }

            S.Add(Start);//把源点加入集合S
            Isfor[Start] = true;//源点已经加入集合S
           
            //将除源点外的其他节点加入集合U
            for (int i = 0; i < row; i++)
            {
                if (i != Start)
                    U.Add(i);
            }
           
            //把源点start到各个顶点的距离添加到distance中
            for (int i = 0; i < row; i++)
            {
                distance[i] = Metro[Start, i];
                //prev[i] = 0;//将所有点的前一个点初始化为0
                prev[i] = Start;
            }

            int Count = U.Count;//集合U中元素的数量
            while (Count > 0)//当集合U中元素个数不为0
            {
                int min_index = (int)U[0];//假设U中第一个数存储的是最小的数的下标，min_index从1开始
                foreach (int r in U)//遍历集合U
                {
                    if (distance[r] < distance[min_index] && !Isfor[r])//如果源点到点r的距离小于到点min_index的，更新min_index
                        min_index = r;                    
                }


                //xc 如果相等  随机选择
                List<int> temp = new List<int>();
                foreach (int r in U) 
                {                                    
                    if (distance[r] == distance[min_index] && !Isfor[r])
                    {
                        temp.Add(r);
                    }
                }               

                //xc随机选择                
                int num = temp.Count;
                if (num == 1)
                {
                    min_index = temp[0];
                }
                else 
                {
                    //随机化
                    Random rd = new Random();
                    int i = rd.Next(0, num);
                    min_index = temp[i];
                }


                S.Add(min_index);//S加入这个最近的点
                Isfor[min_index] = true;
                U.Remove(min_index);//U中移除这个点；
               
                foreach (int r in U)
                {
                    //查找下一行邻接矩阵，如何距离和上一个起点的距离和与数组存储的相比比较小，就更改新的距离和起始点,再比对新的起点到各边的距离
                    if (distance[r] > distance[min_index] + Metro[min_index, r])
                    {
                        distance[r] = distance[min_index] + Metro[min_index, r];
                        prev[r] = min_index;
                    }
                }
                Count = U.Count;//更新U中元素个数
            }
        }

        /// <summary>
        /// 生成具体的路径
        /// </summary>
        private void CreateWay(int Node) 
        {
            for (int i = 0; i < row; i++)
            {
                string Path = "" + Node;//记录到路由表最短路径

                int prePoint = prev[i];
                string s = "";
                StringBuilder sb = new StringBuilder(10);
                while (prePoint != Node)
                {
                    s = prePoint + s;
                    prePoint = prev[prePoint];
                }
                for (int j = 0; j < s.Length; j++)
                {
                    Path = Path + "-" + s[j];
                }

                Path = Path + "-" + i;
                PathRoutingtable[Node, i] = Path;

            }
        }

        /// <summary>
        /// 留给外部的接口，可以用来其他类调用，生成路径规划路由表
        /// </summary>
        public void VehiclePathPlan()
        {
            for (int i = 0; i < row; i++) 
            {
                FindWay(i);
                CreateWay(i);
            }
        }

        //获取路由表
        public static string[,] GetPathRouting() 
        {
            return PathRoutingtable;
        }
    }
}
